We consider the problem of inferring the opinions of a social network throughstrategically sampling a minimum subset of nodes by exploiting correlations innode opinions. We first introduce the concept of information dominating set(IDS). A subset of nodes in a given network is an IDS if knowing the opinionsof nodes in this subset is sufficient to infer the opinion of the entirenetwork. We focus on two fundamental algorithmic problems: (i) given a subsetof the network, how to determine whether it is an IDS; (ii) how to construct aminimum IDS. Assuming binary opinions and the local majority rule for opinioncorrelation, we show that the first problem is co-NP-complete and the secondproblem is NP-hard in general networks. We then focus on networks with specialstructures, in particular, acyclic networks. We show that in acyclic networks,both problems admit linear-complexity solutions by establishing a connectionbetween the IDS problems and the vertex cover problem. Our technique forestablishing the hardness of the IDS problems is based on a novel graphtransformation that transforms the IDS problems in a general network to that inan odd-degree network. This graph transformation technique not only gives anapproximation algorithm to the IDS problems, but also provides a useful toolfor general studies related to the local majority rule. Besides opinionsampling for applications such as political polling and market survey, theconcept of IDS and the results obtained in this paper also find applications indata compression and identifying critical nodes in information networks.
展开▼
